package graph;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.TreeSet;

//Nice iterator
import org.apache.commons.collections.iterators.ArrayListIterator;



public class graph {
 
	private ArrayList<ArrayList<Node>> cycles;
	
	private boolean debug;
	private boolean foundSameCycle = false;
	
	private TreeSet<Node> nodes;
	
	
	public graph(boolean _debug)
	{
		
		nodes = new TreeSet<Node>();
		cycles = new ArrayList<ArrayList<Node>>();
		debug = _debug;
	}
	
	public synchronized void addNode(Node n)
	{
		nodes.add(n);
		
	}
	public synchronized Node findNode(int id)
	{
		Node found = null;
		Iterator<Node> iter = nodes.iterator();
		while(iter.hasNext())
		{
			Node n = iter.next();
			if(n.getID() == id)
				 found = n;
		}
		return found;
	}
	public synchronized void removeNodes(ArrayList<Node> c)
	{
		
		//needs to remove all outs from all its ins...
		for(int i =0; i < c.size(); i++)
		{
			Node n = c.get(i);
			//1st get the ins for this node
			TreeSet<Node> ins = n.getInNeighbors();
			
			//2nd go through ins and remove n
			Iterator<Node> iter = ins.iterator();
			while(iter.hasNext())
			{
				Node tmp = iter.next();
				tmp.removeOutToNode(n);
			}
		}
		
		//finally remove the match from nodes
		nodes.removeAll(c);

		
	}
	
	private synchronized void setAllNodesUnvisited()
	{
		//mark all nodes unvisited
		Iterator<Node> iter = nodes.iterator();
		
		if(debug)
			System.out.println("Setting all to not visited");
		
		while (iter.hasNext()) {
			
			Node tmp = iter.next();
			tmp.setVisited(false);
				
		}//while set as visited
	}

	
	@SuppressWarnings("unchecked")
	public synchronized void findCycle(int where)
	{
		boolean cycleAdded = false;

		LinkedList<Node> toVisit;
		Node oldB = null;

		//This sets up all neighbors for everynode
		this.setupNeighbors();

		//this sets all the nodes to visited
		this.setAllNodesUnvisited();

		//This makes it so the arraylistiterator will work..
		Object[] ns = nodes.toArray();

		//This iterator is for going through all of the nodes
		Iterator<Node> iter = new ArrayListIterator(ns, where);

		System.out.println("Starting Search at " + where);

		while (iter.hasNext()) {


			Node a = iter.next();
			a.setVisited(true);

			a.setStartOfCycle(true);


			if(debug)
			{
				System.out.println("");
				System.out.println("Node a: " + a.getID());
			}




			toVisit = new LinkedList<Node>(a.getOutNeighbors());//This should set our outneighbors to this linked list
			
			boolean firstRun = true;

			while(toVisit.isEmpty() == false)
			{

				
				Node b = toVisit.poll();

				if(debug)
				{
					System.out.println("Node B: " + b.getID());
				}
				
				if(firstRun == true)
				{
					
					b.setLastVisited(a);
					firstRun = false;
				}
				else
				{
					b.setLastVisited(oldB);			
				}
				
				b.setVisited(true);


				TreeSet<Node> nb = b.getOutNeighbors();
				//nb.contains(a)
				//We made it back to the start of our cycle!!

				if( nb.contains(a) )
				{

					Node latest = b;
					ArrayList<Node> cycle = new ArrayList<Node>();
					boolean startOfCycle = false;
					
					
					while(startOfCycle != true)
					{
						if(debug)
							System.out.println("Cycle adding will go in reverse");
						
						cycle.add(latest);
						//WE HAVE A MATCH!!
						if(debug)
						{
							System.out.println("Cycles Adding: " + latest.getID());
						}
						
						//This boolean tells us if we are at the beginning of the cycle
						startOfCycle = latest.getStartOfCycle();
						
						if(startOfCycle == true)
							oldB = latest;
						
						latest = latest.getLastVisited();
						
					}
					
					boolean duplicate = false;
					if(cycle.size() > 0)
					{
						duplicate = this.checkDuplicateCycle(cycle);
					}
					
					if(duplicate == false)
						cycleAdded = true;
					
					if(cycleAdded = true)
					{
						System.out.println("Cycle added of " + cycle.size() + " size.");
						for(int i =0; i < cycle.size(); i++)
						{
							System.out.print(cycle.get(i).getID() + " " );
							if(cycle.get(i).getID() != a.getID())
							{
								cycle.get(i).setVisited(false);//This line ensures other cycles can use this node... d
							}

						}
					}

				}
				else
				{
					
					//IF NB doesn't contain A..
					Iterator<Node> itr = nb.iterator();
					while(itr.hasNext())
					{
						Node n = itr.next();
						if(n.isVisited() == false)
							toVisit.addFirst(n);//This add adds on 
						

					}
					
				}//else
				
				if(cycleAdded == true)
				{
					cycleAdded = false;
				}
				else
					oldB = b;
			}

			//need to set this back to false each time
			a.setStartOfCycle(false);
			oldB = null;

		}//while
			if(debug)
				this.printCycles();
	}//method
	
	private boolean checkDuplicateCycle(ArrayList<Node> _cycle)
	{
		if(cycles.size() == 0)
		{
			cycles.add(_cycle);
		}
		
		else if(cycles.size() > 0)
		{
		
			foundSameCycle = false;
			
			//This loops checks so we don't add the same cycle twice
			for(int i =0; i < cycles.size(); i++)
			{
				if(cycles.get(i).containsAll(_cycle))
				{
					if(debug)
						System.out.println("FOUND THE SAME CYCLE! NOT ADDING!");
					foundSameCycle = true;
				}
			}
		}
		
		if(foundSameCycle == false)
		{
			cycles.add(_cycle);
		}
		
		return foundSameCycle;
	}
	
	
	public synchronized void setupNeighbors()
	{
		
		Iterator<Node> iter = nodes.iterator();
		while (iter.hasNext()) {
			Node currentNode = iter.next();
			
			Iterator<Node> iter2 = nodes.iterator();
			while (iter2.hasNext()) {				//this will cause it to start looking from the beginning again..
				
				Node tmpNode = iter2.next();
		
				if(currentNode.getCount() != tmpNode.getCount())
				{
					
					if(currentNode.getOutString().equalsIgnoreCase(tmpNode.getInString()))
					{
						//Don't add the samething twice
						if(!currentNode.getOutNeighbors().contains(tmpNode))
						{
							currentNode.addOutNeighbors(tmpNode);
							if(debug)
								System.out.println("CurrentNode: " + currentNode.getCount() + " add out: " + tmpNode.getCount());
						}
							
						if(!tmpNode.getInNeighbors().contains(currentNode))
						{
							tmpNode.addInNeighbors(currentNode);
							if(debug)
								System.out.println("tmpNode: " + tmpNode.getCount() + " add in: " + currentNode.getCount());
						}
							
					}
					
					if(currentNode.getInString().equalsIgnoreCase(tmpNode.getOutString()))
					{
						//Don't add the samething twice
						if(!currentNode.getInNeighbors().contains(tmpNode))
						{
							currentNode.addInNeighbors(tmpNode);
							if(debug)
								System.out.println("CurrentNode: " + currentNode.getCount() + " add in: " + tmpNode.getCount());
								
						}
							
						if(!tmpNode.getOutNeighbors().contains(currentNode))
						{
							tmpNode.addOutNeighbors(currentNode);
							if(debug)
								System.out.println("tmpNode: " + tmpNode.getCount() + " add out: " + currentNode.getCount());
						}
						
					}
					
				}//!=
				
			}//innerwhile
			
		}//outter while
		
	}
	
	public synchronized void printCycles()
	{
		for(int i =0; i<cycles.size(); i++)
		{
			for(int j = cycles.get(i).size() -1; j >= 0; j--)
			{
				System.out.println(cycles.get(i).get(j));
			}
			System.out.println("************");
		}
	}
	
	public synchronized ArrayList<ArrayList<Node>> getCycles()
	{
		return cycles;
	}
 
}
